package com.example.learn.red_black_tree;

public class BinarySearchTree extends AbstractTree {
    protected int size;

    public Node insert(int e) {
        elementList.add(e);
        if (root == null) {
            root = new Node(this.getClass(), e, null, null, null);
            size++;
            return root;
        }

        Node parent = root;
        Node search = root;
        while (search != null && search.value != null) {
            parent = search;
            if (e < search.value) {
                search = search.left;
            } else {
                search = search.right;
            }

        }
        Node newNode = new Node(this.getClass(), e, parent, null, null);
        if (parent.value > newNode.value) {
            parent.left = newNode;
        } else {
            parent.right = newNode;
        }
        size++;
        return newNode;


    }

    public Node delete(int e) {
        elementList.remove(e);
        Node delNode = search(e);
        if (delNode == null) {
            return null;
        }
        return delete(delNode);
    }

    public Node search(int e) {
        Node node = root;
        while (node != null && node.value != null && node.value != e) {
            if (e < node.value) {
                node = node.left;
            } else {
                node = node.right;
            }

        }
        return node;
    }

    protected Node delete(Node delNode) {
        if (delNode == null) {
            return null;
        }
        Node result = null;
        //如果待删除节点的左子树为空 则选择 该节点的右子节点代替该节点
        if (delNode.left == null) {
            result = transplant(delNode, delNode.right);
        }
        //如果待删除节点的右子树为空 则选择 该节点的左子节点代替该节点
        else if (delNode.right == null) {
            result = transplant(delNode, delNode.left);
        }
        //如果待删除节点的左右子树都不为空,我们需要找到比当前节点小的最大节点(前驱)来替换该节点
        //又或者比当前节点大的最小节点(后继)来替换该节点
        else {
            Node miniNode = getMiniNode(delNode.right);
            if (miniNode.parent != delNode) {
                //交换位置,将miniNode右子节点来替换miniNode的位置, 因为miniNode是删除节点的右子树中最小节点,所以miniNode.left==null
                transplant(miniNode, miniNode.right);
                miniNode.right  = delNode.right;
                miniNode.right.parent = miniNode;
            }
            //交换位置,删除节点和miniNode
            transplant(delNode,miniNode);
            miniNode.left = delNode.left;
            miniNode.left.parent = miniNode;
            return miniNode;
        }
        size--;
        return result;
    }


    /**
     * 节点替换
     *
     * @param delNode 删除节点
     * @param addNode 替换节点
     * @return
     */
    private Node transplant(Node delNode, Node addNode) {
        if (delNode.parent == null) {
            this.root = addNode;
        } else if (delNode.parent.left == delNode) {
            delNode.parent.left = addNode;
        } else {
            delNode.parent.right = addNode;
        }
        if (addNode != null) {
            addNode.parent = delNode.parent;
        }
        return addNode;

    }

    protected Node getMiniNode(Node node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }

    @Override
    public String toString() {
        String str = elementList.toString();
        str = str.substring(str.indexOf("[") + 1, str.lastIndexOf("]")).replace(" ", "");
        int nullIdx = str.indexOf("null");
        if (nullIdx > 0) {
            str = str.substring(0, str.indexOf("null"));
            str = str.substring(0, str.lastIndexOf(","));
        }
        System.out.println(this.getClass().getSimpleName() + "，输入节点：" + str + "\r\n");
        return printSubTree(root);
    }
}
